package com.heyqing.bruteForce;

/**
 * ClassName:BFBackpack
 * Package:com.heyqing.bruteForce
 * Description:
 *
 * @Date:2024/6/10
 * @Author:Heyqing
 */
public class BFBackpack {
    private int goodsNumber;
    // 物品的重量数组
    private int[] weights;
    // 物品的价值数组
    private int[] values;
    // 背包的容量
    private int capacity;
    // 最大价值
    private int maxValue = 0;

    public BFBackpack(int goodsNumber, int[] weights, int[] values, int capacity) {
        this.goodsNumber = goodsNumber;
        this.weights = weights;
        this.values = values;
        this.capacity = capacity;
    }
    // 递归求解
    private void knapsackRecursive(int index, int currentWeight, int currentValue) {
        // 基准情况：当遍历完所有物品或背包已满时
        if (index == goodsNumber || currentWeight > capacity) {
            // 如果当前价值大于已知的最大价值，则更新
            if (currentValue > maxValue) {
                maxValue = currentValue;
            }
            return;
        }
        // 不选择当前物品
        knapsackRecursive(index + 1, currentWeight, currentValue);
        // 选择当前物品
        if (currentWeight + weights[index] <= capacity) {
            knapsackRecursive(index + 1, currentWeight + weights[index], currentValue + values[index]);
        }
    }
    // 调用递归函数求解
    public int getMaxValue() {
        knapsackRecursive(0, 0, 0);
        return maxValue;
    }
}
